﻿/**
  @(#)$Id: AL_TreeBinSearchSeq.h 86 2013-10-17 11:56:44Z xiaoting $
  @brief	Tree (tree) that contains n (n> 0) nodes of a finite set, where:
	(1) Each element is called node (node);
	(2) there is a particular node is called the root node or root (root).
	(3) In addition to the remaining data elements other than the root node is divided into m (m ≥ 0) disjoint set of T1, T2, ...... 
	Tm-1, wherein each set of Ti (1 <= i <= m ) itself is a tree, the original tree is called a subtree (subtree).
  
  
  Trees can also be defined as: the tree is a root node and several sub-tree consisting of stars. And a tree is a set defined on the 
  set consisting of a relationship. Elements in the collection known as a tree of nodes, the defined relationship is called 
  parent-child relationship. Parent-child relationship between the nodes of the tree establishes a hierarchy. In this there is a 
  hierarchy node has a special status, this node is called the root of the tree, otherwise known as root.

  We can give form to the tree recursively defined as follows:
	Single node is a tree, the roots is the node itself.
	Let T1, T2, .., Tk is a tree, the root node are respectively n1, n2, .., nk. With a new node n as n1, n2, .., nk's father, then 
	get a new tree node n is the new root of the tree. We call n1, n2, .., nk is a group of siblings, they are sub-node n junction. 
	We also said that n1, n2, .., nk is the sub-tree node n.

	Empty tree is also called the empty tree. Air no node in the tree.

 The related concepts of tree 
  1. Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
  2. Height or depth of the tree: the maximum level of nodes in the tree;
  3. Forests: the m (m> = 0) disjoint trees set of trees called forest;

  The related concepts of tree node 
  1.degree		degree node: A node of the subtree containing the number is called the node degree;
  2.leaf			leaf nodes or terminal nodes: degree 0 are called leaf nodes;
  3.branch		non-terminal node or branch node: node degree is not 0;
  4.parent		parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
  5.child			child node or child node: A node subtree containing the root node is called the node's children;
  6.slibing		sibling nodes: nodes with the same parent node is called mutual sibling;
  7.ancestor		ancestor node: from the root to the node through all the nodes on the branch;
  8.descendant	descendant nodes: a node in the subtree rooted at any node is called the node's descendants.

  ////////////////////////////////Binary Search Tree(Binary Sort Tree)//////////////////////////////////////////
  Binary Search Tree(Binary Sort Tree), also known as a binary search tree, also known as binary search tree. It is either empty 
  tree; or a binary tree with the following properties: (1) If the left subtree is not empty, then all nodes in the left sub-tree, 
  the values ​​are less than the value of its root; (2) if the right subtree is not empty, then all nodes in the right subtree are 
  greater than the value of the value of its root; (3) left and right subtrees are also binary sort tree;

  ////////////////////////////////Binary Tree//////////////////////////////////////////
  In computer science, a binary tree is that each node has at most two sub-trees ordered tree. Usually the root of the subtree is 
  called "left subtree" (left subtree) and the "right subtree" (right subtree). Binary tree is often used as a binary search tree 
  and binary heap or a binary sort tree. Binary tree each node has at most two sub-tree (does not exist a degree greater than two 
  nodes), left and right sub-tree binary tree of the points, the order can not be reversed. Binary i-th layer of at most 2 power 
  nodes i -1; binary tree of depth k at most 2 ^ (k) -1 nodes; for any binary tree T, if it is the terminal nodes (i.e. leaf nodes) 
  is, the nodes of degree 2 is, then = + 1.

  ////////////////////////////////Complete Binary Tree//////////////////////////////////////////
  If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of nodes, right to 
  left, the h-layer node number of consecutive missing, this is a complete binary tree .

  ////////////////////////////////Full Binary Tree//////////////////////////////////////////
  A binary tree of height h is 2 ^ h-1 element is called a full binary tree.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-17 19:56:44 +0800 (周四, 17 十月 2013) $
  @Revision $Revision: 86 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeBinSearchSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeBinSearchSeq.h 86 2013-10-17 11:56:44Z xiaoting $
 */

#ifndef CXX_AL_TREEBINSEARCHSEQ_H
#define CXX_AL_TREEBINSEARCHSEQ_H

#ifndef CXX_AL_LISTSEQ_H
#include "AL_ListSeq.h"
#endif

#ifndef CXX_AL_QUEUESEQ_H
#include "AL_QueueSeq.h"
#endif

#ifndef CXX_AL_TREENODEBINSEARCHSEQ_H
#include "AL_TreeNodeBinSearchSeq.h"
#endif

#ifndef CXX_AL_STACKSEQ_H
#include "AL_StackSeq.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_TreeBinSearchSeq
///////////////////////////////////////////////////////////////////////////

template<typename T, typename KEY> 
class AL_TreeBinSearchSeq
{
public:
	static const DWORD TREEBINSEQ_DEFAULTSIZE			= 100;
	static const DWORD TREEBINSEQ_MAXSIZE				= 0xffffffff;
	static const DWORD TREEBINSEQ_HEIGHTINVALID			= 0xffffffff;

	/**
	* Construction
	*
	* @param	DWORD dwSize (default value: TREEBINSEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention
	*/
	AL_TreeBinSearchSeq(DWORD dwSize = TREEBINSEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention 
	*/
	~AL_TreeBinSearchSeq();

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the tree has data?
	* @attention
	*/
	BOOL IsEmpty() const;
	
	/**
	* GetRootNode
	*
	* @param
	* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
	* @note Get the root data
	* @attention 
	*/
	const AL_TreeNodeBinSearchSeq<T, KEY>* GetRootNode() const;

	/**
	* GetDegree
	*
	* @param
	* @return	DWORD
	* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
	* @attention 
	*/
	DWORD GetDegree() const;


	/**
	* GetHeight
	*
	* @param	
	* @return	DWORD
	* @note Height or depth of the tree: the maximum level of nodes in the tree;
	* @attention 
	*/
	DWORD GetHeight() const;

	/**
	* GetNodesNum
	*
	* @param
	* @return	DWORD
	* @note get the notes number of the tree 
	* @attention 
	*/
	DWORD GetNodesNum() const;

	/**
	* Clear
	*
	* @param
	* @return	
	* @note 
	* @attention 
	*/
	VOID Clear();

	/**
	* PreOrderTraversal
	*
	* @param	AL_ListSeq<T>& listOrder <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note Pre-order traversal
	* @attention 
	*/
	BOOL PreOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* InOrderTraversal
	*
	* @param	AL_ListSeq<T>& listOrder <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note In-order traversal
	* @attention 
	*/
	BOOL InOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* PostOrderTraversal
	*
	* @param	AL_ListSeq<T>& listOrder <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note Post-order traversal
	* @attention 
	*/
	BOOL PostOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* LevelOrderTraversal
	*
	* @param	AL_ListSeq<T>& listOrder <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listSibling <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listSibling, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listAncestor <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listAncestor, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<T>& listDescendant <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listDescendant, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;
	
	/**
	* Get
	*
	* @param	const KEY& tKey <IN> 
	* @param	const T& tData <OUT> 
	* @return	BOOL
	* @note
	* @attention
	*/
	BOOL Get(const KEY& tKey, T& tData);

	/**
	* Insert
	*
	* @param	const T& tData <IN> 
	* @param	const KEY& tKey <IN> 
	* @return	BOOL
	* @note
	* @attention
	*/
	BOOL Insert(const T& tData, const KEY& tKey);
	
	/**
	* RemoveNode
	*
	* @param	const KEY& tKey <IN>
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, only remove current node and not include it's descendant note
	*/
	BOOL RemoveNode(const KEY& tKey);


	/**
	* Remove
	*
	* @param	const KEY& tKey <IN>
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, only remove current node and include it's descendant note
	*/
	BOOL Remove(const KEY& tKey);

	/**
	* IsCompleteTreeBin
	*
	* @param
	* @return	BOOL
	* @note Is Complete Binary Tree
	* @attention If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of 
	             nodes, right to left, the h-layer node number of consecutive missing, this is a complete binary tree .
	*/
	BOOL  IsCompleteTreeBin() const;

	/**
	* IsFullTreeBin
	*
	* @param
	* @return	BOOL
	* @note Is Full Binary Tree
	* @attention A binary tree of height h is 2 ^ h-1 element is called a full binary tree.
	*/
	BOOL  IsFullTreeBin() const;

protected:
public:

	/**
	* GetChildNodeLeftAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeBinSearchSeq<T, KEY>* GetChildNodeLeftAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode) const;

	/**
	* GetChildNodeRightAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeBinSearchSeq<T, KEY>*  GetChildNodeRightAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode) const;

	/**
	* GetNode
	*
	* @param	const KEY& tKey <IN> 
	* @return	const AL_TreeNodeBinSearchSeq<T, KEY>* 
	* @note
	* @attention
	*/
	const AL_TreeNodeBinSearchSeq<T, KEY>* GetNode(const KEY& tKey);

	/**
	* GetNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
	* @param	const KEY& tKey <IN> 
	* @return	const AL_TreeNodeBinSearchSeq<T, KEY>* 
	* @note		for Recursion search
	* @attention
	*/
	const AL_TreeNodeBinSearchSeq<T, KEY>* GetNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const KEY& tKey);

	/**
	* Insert
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pRecursionNode <IN> 
	* @param	const T& tData <IN> 
	* @param	const KEY& tKey <IN> 
	* @return	BOOL
	* @note		for Recursion Insert
	* @attention if pRecursionNode may be NULL
	*/
	BOOL Insert(const AL_TreeNodeBinSearchSeq<T, KEY>* pRecursionNode, const T& tData, const KEY& tKey);

	/**
	* InsertLeftAtNode
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @param	const KEY& tKey <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertLeftAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const T& tData, const KEY& tKey);

	/**
	* InsertRightAtNode
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @param	const KEY& tKey <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertRightAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const T& tData, const KEY& tKey);

	/**
	* InsertAtNode
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN>
	* @param	const KEY& tKey <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
	* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, DWORD dwIndex, const T& tData, const KEY& tKey);
	
	/**
	* Remove
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, only remove current node and not include it's descendant note
	1). p a leaf node, just delete the node, and then modify its parent node pointer (note points is the root node and not 
	the root);
	2). p for the single node (ie, only the left subtree or right subtree). Let p and p subtree connected to the node's father, 
	then delete p; (note points is the root node and not the root);
	3). p left subtree and right subtree are not empty. Find p's successor y, because y certainly no left subtree, so you can 
	delete y, and let y father node becomes y's right subtree father node, and use the value of y instead of p values​​; or 
	method two is to find p precursor x, x certainly no right subtree, so you can delete x, and let x, y father node becomes 
	the father of the left subtree of the node;
	*/
	BOOL RemoveNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode);

	/**
	* Remove
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
	*/
	BOOL Remove(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode);

	/**
	* PreOrderTraversal
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note Pre-order traversal
	* @attention
	*/
	BOOL PreOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* InOrderTraversal
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note In-order traversal
	* @attention
	*/
	BOOL InOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* PostOrderTraversal
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note Post-order traversal
	* @attention
	*/
	BOOL PostOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* LevelOrderTraversal
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* PreOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note Pre-order traversal
	* @attention Recursion Traversal
	*/
	BOOL PreOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* InOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note In-order traversal
	* @attention Recursion Traversal
	*/
	BOOL InOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;

	/**
	* PostOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
	* @return	BOOL
	* @note Post-order traversal
	* @attention Recursion Traversal
	*/
	BOOL PostOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const;
	
	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant) const;
	
	/**
	* RecalcDegreeHeight
	*
	* @param	
	* @return	BOOL
	* @note recalculate Degree Height
	* @attention 
	*/
	BOOL RecalcDegreeHeight();

	/**
	* GetListDataFormListNode
	*
	* @param	
	* @param	const AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listNode <IN>
	* @param	AL_ListSeq<T>& listData <OUT>
	* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
	* @note
	* @attention 
	*/
	BOOL GetListDataFormListNode(const AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listNode, AL_ListSeq<T>& listData, AL_ListSeq<KEY>& listKey = AL_ListSeq<KEY>()) const;

	/**
	* GetPrecursor
	*
	* @param const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
	* @param AL_TreeNodeBinSearchSeq<T, KEY>* pQuotePrecursor <OUT>
	* @return BOOL
	* @note Get Precursor of the current tree node
	* @attention Recursion Search
	*/
	BOOL GetPrecursor(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_TreeNodeBinSearchSeq<T, KEY>*& pQuotePrecursor);

	/**
	* GetSuccessor
	*
	* @param const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
	* @param AL_TreeNodeBinSearchSeq<T, KEY>*& pQuoteSuccessor <OUT>
	* @return BOOL
	* @note Get Successor of the current tree node
	* @attention Recursion Search
	*/
	BOOL GetSuccessor(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_TreeNodeBinSearchSeq<T, KEY>*& pQuoteSuccessor);

	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double
	*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;
	
	/**
	*Copy Construct
	*
	* @param	const AL_TreeBinSearchSeq<T, KEY>& cAL_TreeBinSeq
	* @return
	*/
	AL_TreeBinSearchSeq(const AL_TreeBinSearchSeq<T, KEY>& cAL_TreeBinSeq);

	/**
	*Assignment
	*
	* @param	const AL_TreeBinSearchSeq<T, KEY>& cAL_TreeBinSeq
	* @return	AL_TreeBinSearchSeq<T, KEY>&
	*/
	AL_TreeBinSearchSeq<T, KEY>& operator = (const AL_TreeBinSearchSeq<T, KEY>& cAL_TreeBinSeq);

public:
protected:
private:
	AL_TreeNodeBinSearchSeq<T, KEY>*				m_pTreeNode;			
	DWORD								m_dwMaxSize;
	DWORD								m_dwUsed;

	DWORD								m_dwDegree;
	DWORD								m_dwHeight;
	DWORD								m_dwNumNodes;
	AL_TreeNodeBinSearchSeq<T, KEY>*	m_pRootNode;
};

///////////////////////////////////////////////////////////////////////////
//			AL_TreeBinSearchSeq
///////////////////////////////////////////////////////////////////////////

/**
* Construction
*
* @param	DWORD dwSize (default value: TREEBINSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T, typename KEY> 
AL_TreeBinSearchSeq<T, KEY>::AL_TreeBinSearchSeq(DWORD dwSize):
m_pTreeNode(NULL),
m_dwMaxSize(dwSize),
m_dwUsed(0x00),
m_dwDegree(0x00),
m_dwHeight(TREEBINSEQ_HEIGHTINVALID),
m_dwNumNodes(0x00),
m_pRootNode(NULL)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention 
*/
template<typename T, typename KEY> 
AL_TreeBinSearchSeq<T, KEY>::~AL_TreeBinSearchSeq()
{
	if (NULL != m_pTreeNode) {
		delete[] m_pTreeNode;
		m_pTreeNode = NULL;
	}
	m_dwMaxSize = 0x00;
	Clear();
}

/**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note the tree has data?
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::IsEmpty() const
{
	return (0x00 == m_dwNumNodes) ? TRUE:FALSE;
}

/**
* GetRootNode
*
* @param
* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
* @note Get the root data
* @attention 
*/
template<typename T, typename KEY> const AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeBinSearchSeq<T, KEY>::GetRootNode() const
{
	return m_pRootNode;
}

/**
* GetDegree
*
* @param
* @return	DWORD
* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
* @attention 
*/
template<typename T, typename KEY> DWORD 
AL_TreeBinSearchSeq<T, KEY>::GetDegree() const
{
	return m_dwDegree;
}


/**
* GetHeight
*
* @param	
* @return	DWORD
* @note Height or depth of the tree: the maximum level of nodes in the tree;
* @attention 
*/
template<typename T, typename KEY> DWORD 
AL_TreeBinSearchSeq<T, KEY>::GetHeight() const
{
	return m_dwHeight;
}

/**
* GetNodesNum
*
* @param
* @return	DWORD
* @note get the notes number of the tree 
* @attention 
*/
template<typename T, typename KEY> DWORD 
AL_TreeBinSearchSeq<T, KEY>::GetNodesNum() const
{
	return m_dwNumNodes;
}

/**
* Clear
*
* @param
* @return	
* @note 
* @attention 
*/
template<typename T, typename KEY> VOID 
AL_TreeBinSearchSeq<T, KEY>::Clear()
{
	m_dwUsed = 0x00;
	m_dwDegree = 0x00;
	m_dwHeight = TREEBINSEQ_HEIGHTINVALID;
	m_dwNumNodes = 0x00;
	m_pRootNode = NULL;
}

/**
* PreOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note Pre-order traversal
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PreOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == PreOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listKey);
	}

	return FALSE;
}

/**
* InOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note In-order traversal
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == InOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listKey);
	}

	return FALSE;
}

/**
* PostOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note Post-order traversal
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PostOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == PostOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listKey);
	}

	return FALSE;
}

/**
* LevelOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::LevelOrderTraversal(AL_ListSeq<T>& listOrder, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == LevelOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listKey);
	}

	return FALSE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listSibling <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetSiblingAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listSibling, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == GetSiblingAtNode(pCurTreeNode, listNode)) {
		listSibling.Clear();
		return GetListDataFormListNode(listNode, listSibling, listKey);
	}

	return FALSE;
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listAncestor <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetAncestorAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listAncestor, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == GetAncestorAtNode(pCurTreeNode, listNode)) {
		listAncestor.Clear();
		return GetListDataFormListNode(listNode, listAncestor, listKey);
	}

	return FALSE;
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<T>& listDescendant <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetDescendantAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<T>& listDescendant, AL_ListSeq<KEY>& listKey) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNode;
	if (TRUE == GetDescendantAtNode(pCurTreeNode, listNode)) {
		listDescendant.Clear();
		return GetListDataFormListNode(listNode, listDescendant, listKey);
	}

	return FALSE;
}

/**
* Get
*
* @param	const KEY& tKey <IN> 
* @param	const T& tData <OUT> 
* @return	BOOL
* @note
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::Get(const KEY& tKey, T& tData)
{
	const AL_TreeNodeBinSearchSeq<T, KEY>* pGet = GetNode(tKey);
	if (NULL == pGet) {
		//can not get the node
		return FALSE;
	}
	
	//Recursion search
	tData = pGet->GetData();
	return TRUE;
}

/**
* Insert
*
* @param	const T& tData <IN> 
* @param	const KEY& tKey <IN> 
* @return	BOOL
* @note
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::Insert(const T& tData, const KEY& tKey)
{
	//Recursion Insert
	return Insert(m_pRootNode, tData, tKey);
}

/**
* Remove
*
* @param	const KEY& tKey <IN>
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, only remove current node and include it's descendant note
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::Remove(const KEY& tKey)
{
	const AL_TreeNodeBinSearchSeq<T, KEY>* pRemove = GetNode(tKey);
	if (NULL == pRemove) {
		//can not get the node
		return FALSE;
	}

	return Remove(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRemove));
}

/**
* RemoveNode
*
* @param	const KEY& tKey <IN>
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, only remove current node and not include it's descendant note
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::RemoveNode(const KEY& tKey)
{
	const AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveNode = GetNode(tKey);
	if (NULL == pRemoveNode) {
		//can not get the node
		return FALSE;
	}

	return RemoveNode(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRemoveNode));
}


/**
* GetChildNodeRightAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
* @attention
*/
template<typename T, typename KEY> const AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeBinSearchSeq<T, KEY>::GetChildNodeRightAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	return pCurTreeNode->GetChildRight();
}

/**
* GetNode
*
* @param	const KEY& tKey <IN> 
* @return	const AL_TreeNodeBinSearchSeq<T, KEY>* 
* @note
* @attention
*/
template<typename T, typename KEY> const AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeBinSearchSeq<T, KEY>::GetNode(const KEY& tKey)
{
	if (TRUE == IsEmpty()) {
		return NULL;
	}

	if (NULL == m_pRootNode) {
		return NULL;
	}

	return GetNode(m_pRootNode, tKey);
}

/**
* GetNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
* @param	const KEY& tKey <IN> 
* @return	const AL_TreeNodeBinSearchSeq<T, KEY>* 
* @note		for Recursion search
* @attention
*/
template<typename T, typename KEY> const AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeBinSearchSeq<T, KEY>::GetNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const KEY& tKey)
{
	if (NULL == pCurTreeNode) {
		return NULL;
	}

	if (tKey < pCurTreeNode->GetKey()) {
		//search the left child
		return GetNode(pCurTreeNode->GetChildLeft(), tKey);
	}
	else if (pCurTreeNode->GetKey() < tKey) {
		//search the right child
		return GetNode(pCurTreeNode->GetChildRight(), tKey);
	}
	else {
		//find it, pCurTreeNode->GetKey() == tKey
		return pCurTreeNode;
	}
	
	//Recursion End
	return NULL;
}

/**
* IsCompleteTreeBin
*
* @param
* @return	BOOL
* @note Is Complete Binary Tree
* @attention If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of 
             nodes, right to left, the h-layer node number of consecutive missing, this is a complete binary tree .
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::IsCompleteTreeBin() const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	if (NULL == m_pRootNode) {
		return FALSE;
	}
	
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNode;
	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listDescendant;
	if (FALSE == GetDescendantAtNode(m_pRootNode, listDescendant)) {
		return FALSE;
	}

	BOOL bMissing = FALSE;
	for (DWORD dwCnt=0x00; dwCnt<listDescendant->Length(); dwCnt++) {
		if (TRUE ==  listDescendant.Get(pTreeNode, dwCnt)) {
			if (NULL != pTreeNode) {
				if (m_dwHeight > pTreeNode->GetLevel()) {
					//the other layers (1 ~ h-1)
					if (NULL == pTreeNode->GetChildLeft() || NULL == pTreeNode->GetChildRight()) {
						//left or right child not exist!
						return FALSE
					}
				}
				else {
					//the h-layer
					if (TRUE == bMissing) {
						//node number of consecutive missing
						if (NULL == pTreeNode->GetChildLeft() || NULL == pTreeNode->GetChildRight()) {
							//left or right child not exist!
							return FALSE
						}
					}

					if (NULL == pTreeNode->GetChildLeft()) {
						//left child not exist!
						bMissing = TRUE;
						if (NULL != pTreeNode->GetChildRight()) {
							//right child exist!
							return FALSE;
						}
					}
					else {
						//left child exist!
						if (NULL == pTreeNode->GetChildRight()) {
							//right child not exist!
							bMissing = TRUE;
						}
					}
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* IsFullTreeBin
*
* @param
* @return	BOOL
* @note Is Full Binary Tree
* @attention A binary tree of height h is 2 ^ h-1 element is called a full binary tree.
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::IsFullTreeBin() const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	DWORD dwTwo = 2;
	DWORD dwFullTreeBinNum = 1;
	for (DWORD dwFull=0x00; dwFull<GetHeight(); dwFull++) {
		dwFullTreeBinNum *= 2;
	}
	dwFullTreeBinNum -= 1;

	return (dwFullTreeBinNum == GetNodesNum())  ? TRUE:FALSE;
}

/**
* GetChildNodeLeftAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeBinSearchSeq<T, KEY>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> const AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeBinSearchSeq<T, KEY>::GetChildNodeLeftAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	return pCurTreeNode->GetChildLeft();
}

/**
* Insert
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pRecursionNode <IN> 
* @param	const T& tData <IN> 
* @param	const KEY& tKey <IN> 
* @return	BOOL
* @note		for Recursion Insert
* @attention if pRecursionNode may be NULL
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::Insert(const AL_TreeNodeBinSearchSeq<T, KEY>* pRecursionNode, const T& tData, const KEY& tKey)
{
	if (TRUE == IsEmpty()) {
		if (NULL != pRecursionNode) {
			//empty, but has the node
			return FALSE;
		}
		//has no root node, insert as root node
		return InsertAtNode(NULL, 0x00, tData, tKey);
	}
	
	static const AL_TreeNodeBinSearchSeq<T, KEY>* pRecursionNodePre = NULL;		//store the previous node of recursion
	if (NULL == pRecursionNode) {
		if (NULL == pRecursionNodePre) {
			//some thing wrong
			return FALSE;
		}
		//inset to the current tree node
		if (NULL == pRecursionNodePre->GetChildLeft() && NULL == pRecursionNodePre->GetChildRight()) {
			//left and right all NULL
			if (tKey < pRecursionNodePre->GetKey()) {
				//insert the left child
				return InsertLeftAtNode(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRecursionNodePre), tData, tKey);
			}
			else if (pRecursionNodePre->GetKey() < tKey) {
				//insert the right child
				return InsertRightAtNode(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRecursionNodePre), tData, tKey);
			}
			else {
				//error, can not have the same key
				return FALSE;
			}
		}
		else if (NULL == pRecursionNodePre->GetChildLeft() && NULL != pRecursionNodePre->GetChildRight()) {
			//left NULL, right not NULL
			if (tKey < pRecursionNodePre->GetKey()) {
				//insert the left child
				return InsertLeftAtNode(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRecursionNodePre), tData, tKey);
			}
			else {
				//error, can not have the same key
				return FALSE;
			}
		}
		else if (NULL != pRecursionNodePre->GetChildLeft() && NULL == pRecursionNodePre->GetChildRight()) {
			//left not NULL, right NULL
			if (pRecursionNodePre->GetKey() < tKey) {
				return InsertRightAtNode(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pRecursionNodePre), tData, tKey);
			}
			else {
				return FALSE;
			}
		}
		else {
			//left not NULL, right not NULL
			return FALSE;
		}
	}
	pRecursionNodePre = pRecursionNode;
	if (tKey < pRecursionNode->GetKey()) {
		//recursion the left child (Insert)
		return Insert(pRecursionNode->GetChildLeft(), tData, tKey);
// 		if (FALSE == Insert(pRecursionNode->GetChildLeft(), tData, tKey)) {
// 			return FALSE;
// 		}
	}
	else if (pRecursionNode->GetKey() < tKey) {
		//recursion the right child (Insert)
		return Insert(pRecursionNode->GetChildRight(), tData, tKey);
// 		if (FALSE == Insert(pRecursionNode->GetChildRight(), tData, tKey)) {
// 			return FALSE;
// 		}
	}
	else {
		//error, can not have the same key
		return FALSE;
	}

	//Recursion End
	return FALSE;
}

/**
* InsertLeftAtNode
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @param	const KEY& tKey <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InsertLeftAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const T& tData, const KEY& tKey)
{
	return InsertAtNode(pCurTreeNode, 0x00, tData, tKey);
}

/**
* InsertRightAtNode
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @param	const KEY& tKey <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InsertRightAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, const T& tData, const KEY& tKey)
{
	return InsertAtNode(pCurTreeNode, 0x01, tData, tKey);
}

/**
* InsertAtNode
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN>
* @param	const KEY& tKey <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InsertAtNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, DWORD dwIndex, const T& tData, const KEY& tKey)
{
	if (TRUE == IsEmpty()) {
		if (NULL != pCurTreeNode) {
			//error can not insert to the current node pCurTreeNode, is not exist in the tree
			return FALSE;
		}
		else {
			m_pTreeNode[m_dwUsed].SetData(tData);
			m_pTreeNode[m_dwUsed].SetKey(tKey);
			m_pTreeNode[m_dwUsed].SetLevel(0x00);

			m_pRootNode = &m_pTreeNode[m_dwUsed];
			m_dwUsed++;
			m_dwDegree = 0x00;
			m_dwHeight = 0x00;			//empty tree 0xffffffff (-1)
			m_dwNumNodes++;
			return TRUE;
		}
	}

	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if (TRUE == IsFull()) {
		// full, need to get more work buffer 
		//can not support Dynamic Expansion
		return FALSE;
		GetBuffer();
	}

	//inset to the current tree node
	m_pTreeNode[m_dwUsed].SetData(tData);
	m_pTreeNode[m_dwUsed].SetKey(tKey);
	m_pTreeNode[m_dwUsed].SetLevel(pCurTreeNode->GetLevel() + 1);
	if (FALSE ==  pCurTreeNode->Insert(dwIndex, &m_pTreeNode[m_dwUsed])) {
		return FALSE;
	}

	DWORD dwCurNodeDegree = 0x00;
	//loop all node to get the current node degree
	if (m_dwDegree < pCurTreeNode->GetDegree()) {
		m_dwDegree = pCurTreeNode->GetDegree();
	}

	if (m_dwHeight < m_pTreeNode[m_dwUsed].GetLevel()) {
		m_dwHeight = m_pTreeNode[m_dwUsed].GetLevel();
	}
	m_dwUsed++;
	m_dwNumNodes++;

	return TRUE;
}

/**
* Remove
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, only remove current node and not include it's descendant note
			1). p a leaf node, just delete the node, and then modify its parent node pointer (note points is the root node and not 
			the root);
			2). p for the single node (ie, only the left subtree or right subtree). Let p and p subtree connected to the node's father, 
			then delete p; (note points is the root node and not the root);
			3). p left subtree and right subtree are not empty. Find p's successor y, because y certainly no left subtree, so you can 
			delete y, and let y father node becomes y's right subtree father node, and use the value of y instead of p values​​; or 
			method two is to find p precursor x, x certainly no right subtree, so you can delete x, and let x, y father node becomes 
			the father of the left subtree of the node;
*/
template<typename T, typename KEY> BOOL
AL_TreeBinSearchSeq<T, KEY>::RemoveNode(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	
	AL_TreeNodeBinSearchSeq<T, KEY>* pCurNodeParent = NULL;
	if (TRUE == pCurTreeNode->IsLeaf()) {
//	if (0x00 == pCurTreeNode->GetDegree()) {
		//leaf node; see 1)
		pCurNodeParent = pCurTreeNode->GetParent();
		if (NULL != pCurNodeParent) {
			if (FALSE == pCurNodeParent->Remove(pCurTreeNode)) {
				return FALSE;
			}
		}
		else {
			//root node
			if (m_pRootNode == pCurTreeNode) {
				//judge root node
				m_pRootNode = NULL;
			}
			else {
				return FALSE;
			}
		}
	}
	else if (0x01 == pCurTreeNode->GetDegree()) {
		//not leaf node, single node; see 2)
		//get the child node
		AL_TreeNodeBinSearchSeq<T, KEY>* pChildeNode = NULL;
		if (NULL != pCurTreeNode->GetChildLeft()) {
			//left child exist
			pChildeNode = pCurTreeNode->GetChildLeft();
		}
		if (NULL != pCurTreeNode->GetChildRight()) {
			//right child exist
			pChildeNode = pCurTreeNode->GetChildRight();
		}
		
		if (NULL ==  pChildeNode) {
			//can not get child node
			return FALSE;
		}
		pChildeNode->RemoveParent();

		pCurNodeParent = pCurTreeNode->GetParent();
		if (NULL != pCurNodeParent) {
			if (pCurTreeNode == pCurNodeParent->GetChildLeft()) {
				//current node as child left exist
				pCurNodeParent->Remove(pCurTreeNode);
				if (FALSE == pCurNodeParent->InsertLeft(pChildeNode)) {
					return FALSE;
				}
			}
			else {
				//current node as child right exist
				pCurNodeParent->Remove(pCurTreeNode);
				if (FALSE == pCurNodeParent->InsertRight(pChildeNode)) {
					return FALSE;
				}
			}
		}
		else {
			//root node
			if (m_pRootNode == pCurTreeNode) {
				//judge root node
				m_pRootNode = pChildeNode;
			}
			else {
				return FALSE;
			}
		}
	}
	else if (0x02 == pCurTreeNode->GetDegree()){
		// left and right are not empty; see 3)
		AL_TreeNodeBinSearchSeq<T, KEY>* pChildLeft = pCurTreeNode->GetChildLeft();
		AL_TreeNodeBinSearchSeq<T, KEY>* pChildRight = pCurTreeNode->GetChildRight();
		if (NULL ==  pChildLeft|| NULL == pChildRight) {
			//the left or right child not exist
			return FALSE;
		}
		AL_TreeNodeBinSearchSeq<T, KEY>* pReplace = NULL;
		if (FALSE == GetSuccessor(pChildLeft, pReplace)) {
			//get the successor failed
			return FALSE;
		}
		if (NULL == pReplace) {
			//get the successor failed
			return FALSE;
		}

		//pReplace must have not the right child
		if (NULL != pReplace->GetChildRight()) {
			//judge it
			return FALSE;
		}

		AL_TreeNodeBinSearchSeq<T, KEY>* pReplaceParent = pReplace->GetParent();
		if (NULL == pReplaceParent) {
			return FALSE;
		}
		AL_TreeNodeBinSearchSeq<T, KEY>* pReplaceChildLeft = pReplace->GetChildLeft();
		if (FALSE == pReplaceParent->Remove(pReplace) 
			|| FALSE == pReplace->RemoveParent() 
			|| FALSE == pReplace->Remove(pReplaceChildLeft)) {
			return FALSE;
		}
	
		if (NULL != pReplaceChildLeft) {
			//left child exist
			pReplaceChildLeft->RemoveParent();
			if (FALSE == pReplaceParent->InsertRight(pReplaceChildLeft)) {
				return FALSE;
			}
		}

		//insert current node's child to the replace node
		pChildLeft->RemoveParent();
		pChildRight->RemoveParent();
		if (pReplace != pChildLeft) {
			if (FALSE == pReplace->InsertLeft(pChildLeft)) {
					return FALSE;
			}
		}
		if (pReplace != pChildRight) {
			if (FALSE == pReplace->InsertRight(pChildRight)) {
				return FALSE;
			}
		}
		
		pCurNodeParent = pCurTreeNode->GetParent();
		if (NULL != pCurNodeParent) {
			//current node has parent
			if (pCurTreeNode == pCurNodeParent->GetChildLeft()) {
				//current node as child left exist
				pCurNodeParent->Remove(pCurTreeNode);
				if (FALSE == pCurNodeParent->InsertLeft(pReplace)) {
					return FALSE;
				}
			}
			else {
				//current node as child right exist
				pCurNodeParent->Remove(pCurTreeNode);
				if (FALSE == pCurNodeParent->InsertRight(pReplace)) {
					return FALSE;
				}
			}
		}
		else {
			if (m_pRootNode == pCurTreeNode) {
				//root node
				m_pRootNode = pReplace;
			}
			else {
				return FALSE;
			}
		}
	}
	else {
		//Binary Search Tree only two child node, can not be this case
		return FALSE;
	}	

	//delete the current node
	pCurTreeNode->Clear();
	m_dwNumNodes--;
	return TRUE;
}

/**
* Remove
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
*/
template<typename T, typename KEY> BOOL
AL_TreeBinSearchSeq<T, KEY>::Remove(AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listTreeNodeDescendant;
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNodeDescendant = NULL;
	if (TRUE == pCurTreeNode->GetDescendant(listTreeNodeDescendant)) {
		//delete the descendant node
		for (DWORD dwRemoveCnt=0x00; dwRemoveCnt<listTreeNodeDescendant.Length(); dwRemoveCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwRemoveCnt, pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					pTreeNodeDescendant->Clear();
				}
				else {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
	}

	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeParent = pCurTreeNode->GetParent();
	if (NULL == pNodeParent && m_pRootNode != pCurTreeNode) {
		//not root node and has no parent node
		return FALSE;
	}
	if (NULL != pNodeParent) {
		//parent exist, remove the child node (pCurTreeNode)
		pNodeParent->Remove(pCurTreeNode);
	}
	
	if (m_pRootNode == pCurTreeNode) {
		//remove the root node
		m_pRootNode = NULL;
	}

	pCurTreeNode->Clear();
	m_dwNumNodes -= (listTreeNodeDescendant.Length() + 1);

	if (FALSE == RecalcDegreeHeight()) {
		return FALSE;
	}
	return TRUE;
}

/**
* PreOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note Pre-order traversal
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PreOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	return PreOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> cStack;
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNode = const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode);

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			listOrder.InsertEnd(pTreeNode);
			if (NULL != pTreeNode->GetChildRight()) {
				//push the child right to stack
				cStack.Push(pTreeNode->GetChildRight());
			}
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL == pTreeNode) {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}

	}
	return TRUE;
}

/**
* InOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note In-order traversal
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	return InOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> cStack;
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNode = const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode);

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode);
				if (NULL != pTreeNode->GetChildRight()){
					//child right exist, push the node, and loop it's left child to push
					pTreeNode = pTreeNode->GetChildRight();
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* PostOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note Post-order traversal
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PostOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	return PostOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> cStack;
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNode = const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode);
	AL_StackSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> cStackReturn;
	AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNodeReturn = NULL;

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			if (NULL != pTreeNode->GetChildLeft()) {
				pTreeNode = pTreeNode->GetChildLeft();
			}
			else {
				//has not left child, get the right child
				pTreeNode = pTreeNode->GetChildRight();
			}
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode);
				if (NULL != pTreeNode->GetChildLeft() && NULL != pTreeNode->GetChildRight()){
					//child right exist
					cStackReturn.Top(pTreeNodeReturn);
					if (pTreeNodeReturn != pTreeNode) {
						listOrder.RemoveAt(listOrder.Length()-1);
						cStack.Push(pTreeNode);
						cStackReturn.Push(pTreeNode);
						pTreeNode = pTreeNode->GetChildRight();
					}
					else {
						//to pop the node in the stack
						cStackReturn.Pop(pTreeNodeReturn);
						pTreeNode = NULL;
					}
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* LevelOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::LevelOrderTraversal(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	listOrder.Clear();
	/*
	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listNodeOrder;
	listNodeOrder.InsertEnd(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode));
	//loop the all node
	DWORD dwNodeOrderLoop = 0x00;
	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeOrderChild = NULL;
	while (TRUE == listNodeOrder.Get(pNodeOrderLoop, dwNodeOrderLoop)) {
		dwNodeOrderLoop++;
		if (NULL != pNodeOrderLoop) {
			listOrder.InsertEnd(pNodeOrderLoop);
			pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
			pNodeOrderChild = pNodeOrderLoop->GetChildRight();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
	*/
	
	AL_QueueSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> queueOrder;
	queueOrder.Push(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode));
	
	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeOrderChild = NULL;
	while (FALSE == queueOrder.IsEmpty()) {
		if (TRUE == queueOrder.Pop(pNodeOrderLoop)) {
			if (NULL != pNodeOrderLoop) {
				listOrder.InsertEnd(pNodeOrderLoop); 
				pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
				pNodeOrderChild = pNodeOrderLoop->GetChildRight();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

/**
* PreOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note Pre-order traversal
* @attention Recursion Traversal
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PreOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode))) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == PreOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}	
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == PreOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Recursion End
	return TRUE;
}

/**
* InOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note In-order traversal
* @attention Recursion Traversal
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::InOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == InOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode))) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == InOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Recursion End
	return TRUE;
}

/**
* PostOrderTraversal
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder <OUT>
* @return	BOOL
* @note Post-order traversal
* @attention Recursion Traversal
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::PostOrderTraversalRecursion(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == PostOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == PostOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode))) {
		return FALSE;
	}

	//Recursion End
	return TRUE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetSiblingAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	
	listSibling.Clear();
	return pCurTreeNode->GetSibling(listSibling);
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetAncestorAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listAncestor.Clear();
	return pCurTreeNode->GetAncestor(listAncestor);
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN> 
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetDescendantAtNode(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listDescendant.Clear();
	return pCurTreeNode->GetDescendant(listDescendant);
}

/**
* RecalcDegreeHeight
*
* @param	
* @return	BOOL
* @note recalculate Degree Height
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::RecalcDegreeHeight()
{
	if (NULL == m_pRootNode) {
		if (TRUE == IsEmpty()) {
			m_dwDegree = 0x00;
			m_dwHeight = TREEBINSEQ_HEIGHTINVALID;
			return TRUE;
		}
		else {
			return FALSE;
		}
	}
	m_dwDegree = m_pRootNode->GetDegree();
	m_dwHeight = m_pRootNode->GetLevel();

	//loop all the node
	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listTreeNodeDescendant;
	if (TRUE == m_pRootNode->GetDescendant(listTreeNodeDescendant)) {
		DWORD dwNumNodes = listTreeNodeDescendant.Length() + 1;
		if (m_dwNumNodes != dwNumNodes) {
			return FALSE;
		}

		AL_TreeNodeBinSearchSeq<T, KEY>* pTreeNodeDescendant = NULL;
		for (DWORD dwLoopCnt=0x00; dwLoopCnt<listTreeNodeDescendant.Length(); dwLoopCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwLoopCnt, pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					if (m_dwDegree < pTreeNodeDescendant->GetDegree()) {
						m_dwDegree = pTreeNodeDescendant->GetDegree();
					}
					if (m_dwHeight < pTreeNodeDescendant->GetLevel()) {
						m_dwHeight = pTreeNodeDescendant->GetLevel();
					}
				}
				else {
					//error
					return FALSE;
				}
			}
			else {
				//error
				return FALSE;
			}
		}
	}
	return TRUE;
}

/**
* GetListDataFormListNode
*
* @param	
* @param	const AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listNode <IN>
* @param	AL_ListSeq<T>& listData <OUT>
* @param	AL_ListSeq<KEY>& listKey <OUT> (default value: AL_ListSeq<KEY>())
* @note
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetListDataFormListNode(const AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listNode, AL_ListSeq<T>& listData, AL_ListSeq<KEY>& listKey) const
{
	AL_TreeNodeBinSearchSeq<T, KEY>* pNodeLoop = NULL;
	listData.Clear();
	listKey.Clear();
	//loop all node in list
	for (DWORD dwLoopCnt=0x00; dwLoopCnt<listNode.Length(); dwLoopCnt++) {
		if (TRUE == listNode.Get(dwLoopCnt, pNodeLoop)) {
			if (NULL != pNodeLoop) {
				if (FALSE == listData.InsertEnd(pNodeLoop->GetData()) 
					|| FALSE == listKey.InsertEnd(pNodeLoop->GetKey())) {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

/**
* GetPrecursor
*
* @param const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
* @param AL_TreeNodeBinSearchSeq<T, KEY>*& pQuotePrecursor <OUT>
* @return BOOL
* @note Get Precursor of the current tree node
* @attention Recursion Search
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetPrecursor(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_TreeNodeBinSearchSeq<T, KEY>*& pQuotePrecursor)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if (NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == GetSuccessor(pCurTreeNode->GetChildLeft(), pQuotePrecursor)) {
			return FALSE;
		}
	}
	else {
		pQuotePrecursor = const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode);
	}
	return TRUE;
}

/**
* GetSuccessor
*
* @param const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode <IN>
* @param AL_TreeNodeBinSearchSeq<T, KEY>*& pQuoteSuccessor <OUT>
* @return BOOL
* @note Get Successor of the current tree node
* @attention Recursion Search
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::GetSuccessor(const AL_TreeNodeBinSearchSeq<T, KEY>* pCurTreeNode, AL_TreeNodeBinSearchSeq<T, KEY>*& pQuoteSuccessor)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if (NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == GetSuccessor(pCurTreeNode->GetChildRight(), pQuoteSuccessor)) {
			return FALSE;
		}
	}
	else {
		pQuoteSuccessor = const_cast<AL_TreeNodeBinSearchSeq<T, KEY>*>(pCurTreeNode);
	}
	return TRUE;
}

/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T, typename KEY> VOID 
AL_TreeBinSearchSeq<T, KEY>::GetBuffer()
{
	if ( (FALSE == IsFull()) && (NULL != m_pTreeNode) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pTreeNode) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pTreeNode = new AL_TreeNodeBinSearchSeq<T, KEY>[m_dwMaxSize];
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	AL_TreeNodeBinSearchSeq<T, KEY>* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pTreeNode;
	if (TREEBINSEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (TREEBINSEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = TREEBINSEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pTreeNode = new AL_TreeNodeBinSearchSeq<T, KEY>[m_dwMaxSize];
	}
	//need to copy the last to the current
	for (DWORD dwCpy=0x00; dwCpy<GetNodesNum(); dwCpy++) {
		m_pTreeNode[dwCpy] = pLastTpye[dwCpy];
	}

	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param VOID
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeBinSearchSeq<T, KEY>::IsFull() const
{
	return (m_dwMaxSize <= GetNodesNum()) ? TRUE:FALSE;
}
#endif // CXX_AL_TREEBINSEARCHSEQ_H
/* EOF */